import System (getArgs)
import System.Random

cabe quadro (lin,col,dir_v,dir_h) [] = True 
cabe quadro (_,_,0,0) _ = False
cabe quadro (lin,col,dir_v,dir_h) (a:x)
 |(lin < 0) || (lin > ((length quadro)-1)) || (col < 0) || (col > ((length (head quadro))-1))  = False
 |otherwise = cabe quadro (lin + dir_v,col + dir_h,dir_v,dir_h) x

encaixa _ _ [] = True
encaixa quadro (lin,col,dir_v,dir_h) (a:x) = ((pegaletra lin col quadro) == ' ' || (pegaletra lin col quadro) == a) && (encaixa quadro (lin + dir_v,col + dir_h,dir_v,dir_h) x)
 where pegaletra lin col quadro = head (drop col (quadro!!lin))

valida :: [String] -> (Int,Int,Int,Int) -> String -> Bool
valida quadro (lin,col,dir_v,dir_h) palavra
 |(cabe quadro (lin,col,dir_v,dir_h) palavra) = encaixa quadro (lin,col,dir_v,dir_h) palavra
 |otherwise = False

inserir :: [String] -> (Int, Int, Int, Int) -> String -> [String]
inserir quadro _ [] = quadro
inserir quadro (lin,col,dir_v,dir_h) (a:x) = inserir (antes ++ [meio] ++ depois) (lin+dir_v,col+dir_h,dir_v,dir_h) x
 where 
  antes = take lin quadro
  meio = (take col (quadro!!lin)) ++ [a] ++ (drop (col+1) (quadro!!lin))
  depois = drop (lin+1) quadro

escolhe_pos (rdv:rdvs) (rdh:rdhs) (rl:rls) (rc:rcs) quadro palavra
 |valida quadro (rl,rc,rdv,rdh) palavra = (rl,rc,rdv,rdh)
 |otherwise = escolhe_pos rdvs rdhs rls rcs quadro palavra

insere :: [Int] -> [Int] -> [Int] -> [Int] -> [String] -> String -> [String]
insere rdv rdh rl rc quadro palavra = inserir quadro (escolhe_pos rdv rdh rl rc quadro palavra) palavra

letras _ [] = []
letras (r:z) (a:x)
 |a == ' ' = ("AAAAAAAAAAAAAAAEEEEEEEEEEEEEOOOOOOOOOOSSSSSSSSRRRRRRRIIIIIIDDDDDNNNNNMMMMMUUUUTTTTCCCLLLPPVVHGBQFZJX"!!r):(letras z x)
 |otherwise = a:(letras z x)

main = do
         argumentos <- getArgs
         let linhas = read (argumentos!!0) :: Int
         let colunas = read (argumentos!!1) :: Int
         let palavras = drop 2 argumentos
         g <- newStdGen
         let r_dir_v = randomRs (-1,1) g
         g <- newStdGen
         let r_dir_h = randomRs (-1,1) g
         g <- newStdGen
         let r_linhas = randomRs (0,(linhas-1)) g
         g <- newStdGen
         let r_colunas = randomRs (0,(colunas-1)) g
         g <- newStdGen
         let r_letra = (randomRs (0,99) g)
         let quadro = replicate linhas (replicate colunas ' ')
         putStrLn (letras r_letra (unlines (foldl (insere r_dir_v r_dir_h r_linhas r_colunas) quadro palavras)))
         putStrLn "Gabarito:"
         putStrLn (unlines (foldl (insere r_dir_v r_dir_h r_linhas r_colunas) quadro palavras))